package wheel.arithmetic;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;

/**
 * 插入排序-简单插入排序
 *
 * 思路：
 * 遍历需要排序的数组
 * 在新数组末尾插入一个数，和前面的数作比较，大于则完成本次插入，小于则继续向前比较，直到不再小于然后将数组数据后移并插入此位置。
 */
public class SimpleInsertSort {

    public static void main(String[] args) {

        Integer[] arr = new Integer[100000];
        for(int i=0; i<arr.length; i++){
            arr[i] = RandomUtil.randomInt(0, arr.length*100);
        }

//        arr = new Integer[]{10, 9, 8, 7, 6, 5, 4, 3};


//        System.out.println("输入: "+ArrayUtil.toString(arr));


        long startTime = System.currentTimeMillis();
        arr = execute(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("耗时: "+(endTime-startTime)+"ms");

//        System.out.println("输出: "+ArrayUtil.toString(arr));

    }

    public static Integer[] execute(Integer[] arr){
        int len = arr.length;
        Integer[] result = new Integer[len];

        result[0] = arr[0];

        for(int i=1; i<len; i++){
            int curr = arr[i];
            int currIndex = i;
            for(int j=i-1; j>=0; j--){
                if(curr<result[j]){
                    currIndex = j;
                }else
                    break;
            }
            //数组数据后移并插入
            System.arraycopy(result, currIndex, result, currIndex+1, i-currIndex);
            result[currIndex] = curr;


        }

        return result;
    }

    //耗时: 35ms 38ms 48ms 一万个
    //耗时: 4898ms 4827ms 4950ms 十万个
    //耗时: 20792ms 23684ms 21203ms 二十万个

}
